Gty的二逼妹子序列

Time Limit: 80 Sec Memory Limit: 28 MB

Description

Autumn和Bakser又在研究Gty的妹子序列了！但他们遇到了一个难题。

对于一段妹子们，他们想让你帮忙求出这之内美丽度∈[a,b]的妹子的美丽度的种类数。

为了方便，我们规定妹子们的美丽度全都在[1,n]中。

给定一个长度为n的正整数序列s(1<=si<=n)，对于m次询问“l,r,a,b”，每次输出sl…sr中，权值∈[a,b]的权值的种类数。

Input

第一行包括两个整数n,m,表示数列s中的元素数和询问数。

第二行包括n个整数s1…sn(1<=si<=n)。

接下来m行,每行包括4个整数l,r,a,b(1<=l<=r<=n,1<=a<=b<=n),意义见题目描述。

保证涉及的所有数在C++的int内。

保证输入合法。

Output

对每个询问，单独输出一行，表示sl…sr中权值∈[a,b]的权值的种类数。

Sample Input

10 10
　4 4 5 1 4 1 5 1 2 1
　5 9 1 2
　3 4 7 9
　4 4 2 5
　2 3 4 7
　5 10 4 4
　3 9 1 1
　1 4 5 9
　8 9 3 3
　2 2 1 6
　8 9 1 4

Sample Output

2
　0
　0
　2
　1
　1
　1
　0
　1
　2

HINT

1<=n<=100000,1<=m<=1000000

Main idea

求区间[l,r]内，权值在[a,b]内的权值种数。

Solution

我们直接运用莫队算法，对权值分块，记录C[x]表示权值x的个数，Bc[x]表示块x内权值在a~b中的种数。

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
#include<bits/stdc++.h>
using namespace std;
typedef long long s64;

const int ONE = 100005;
const int INF = 2147483640;

int n,m,Q;
int a[ONE],block[ONE];
int C[ONE],Bc[ONE];
int Ans[ONE*10];

struct power
{
    int id;
    int l,r,a,b;
}oper[ONE*10];

int get()
{
    int res=1,Q=1;  char c;
    while( (c=getchar())<48 || c>57)
        if(c=='-')Q=-1;
    if(Q) res=c-48;
    while((c=getchar())>=48 && c<=57)
        res=res*10+c-48;
    return res*Q;
}

int cmp(const power &a,const power &b)
{
    if(block[a.l] != block[b.l]) return block[a.l] < block[b.l];
    return a.r < b.r;
}

void increa(int x) {C[x]++; if(C[x]==1) Bc[block[x]]++;}
void reduce(int x) {C[x]--; if(C[x]==0) Bc[block[x]]--;}

int Query(int a,int b)
{
    int res = 0;
    if(block[a] == block[b])
    {
        for(int i=a;i<=b;i++)
            res += C[i]>=1;
        return res;
    }

    for(int i=block[a]+1; i<=block[b]-1; i++) res += Bc[i];
    for(int i=a; i<=block[a]*Q; i++)        res += C[i]>=1;
    for(int i=(block[b]-1)*Q+1; i<=b; i++)    res += C[i]>=1;
    return res;
}

int main()
{
    n = get();    m = get();
    Q = sqrt(n);
    for(int i=1;i<=n;i++) a[i]=get(), block[i] = (i-1)/Q+1;

    for(int i=1;i<=m;i++)
    {
        oper[i].id = i;
        oper[i].l = get();    oper[i].r = get();
        oper[i].a = get();    oper[i].b = get();
    }
    sort(oper+1, oper+m+1, cmp);

    int l = 1, r = 0;
    for(int i=1;i<=m;i++)
    {
        while(r < oper[i].r) increa(a[++r]);
        while(oper[i].l < l) increa(a[--l]);
        while(r > oper[i].r) reduce(a[r--]);
        while(oper[i].l > l) reduce(a[l++]);
        Ans[oper[i].id] = Query(oper[i].a, oper[i].b);
    }

    for(int i=1;i<=m;i++)
        printf("%d\n", Ans[i]);

}